home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / btree / bt_open.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  12.3 KB  |  526 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_open.c    8.3 (Berkeley) 9/16/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. /*
  46.  * Implementation of btree access method for 4.4BSD.
  47.  *
  48.  * The design here was originally based on that of the btree access method
  49.  * used in the Postgres database system at UC Berkeley.  This implementation
  50.  * is wholly independent of the Postgres code.
  51.  */
  52.  
  53. #include <sys/param.h>
  54. #include <sys/stat.h>
  55.  
  56. #include <errno.h>
  57. #include <fcntl.h>
  58. #include <limits.h>
  59. #include <signal.h>
  60. #include <stdio.h>
  61. #include <stdlib.h>
  62. #include <string.h>
  63. #include <unistd.h>
  64.  
  65. #ifdef macintosh
  66. #include <sys/fcntl.h>
  67. #include <sys/errno.h>
  68. #endif
  69.  
  70. #define    __DBINTERFACE_PRIVATE
  71. #include <db.h>
  72. #include "btree.h"
  73.  
  74. static int byteorder __P((void));
  75. static int nroot __P((BTREE *));
  76. static int tmp __P((void));
  77.  
  78. /*
  79.  * __BT_OPEN -- Open a btree.
  80.  *
  81.  * Creates and fills a DB struct, and calls the routine that actually
  82.  * opens the btree.
  83.  *
  84.  * Parameters:
  85.  *    fname:    filename (NULL for in-memory trees)
  86.  *    flags:    open flag bits
  87.  *    mode:    open permission bits
  88.  *    b:    BTREEINFO pointer
  89.  *
  90.  * Returns:
  91.  *    NULL on failure, pointer to DB on success.
  92.  *
  93.  */
  94. DB *
  95. __bt_open(fname, flags, mode, openinfo, dflags)
  96.     const char *fname;
  97.     int flags, mode, dflags;
  98.     const BTREEINFO *openinfo;
  99. {
  100.     BTMETA m;
  101.     BTREE *t;
  102.     BTREEINFO b;
  103.     DB *dbp;
  104.     pgno_t ncache;
  105.     struct stat sb;
  106.     int machine_lorder, nr;
  107.  
  108.     t = NULL;
  109.  
  110.     /*
  111.      * Intention is to make sure all of the user's selections are okay
  112.      * here and then use them without checking.  Can't be complete, since
  113.      * we don't know the right page size, lorder or flags until the backing
  114.      * file is opened.  Also, the file's page size can cause the cachesize
  115.      * to change.
  116.      */
  117.     machine_lorder = byteorder();
  118.     if (openinfo) {
  119.         b = *openinfo;
  120.  
  121.         /* Flags: R_DUP. */
  122.         if (b.flags & ~(R_DUP))
  123.             goto einval;
  124.  
  125.         /*
  126.          * Page size must be indx_t aligned and >= MINPSIZE.  Default
  127.          * page size is set farther on, based on the underlying file
  128.          * transfer size.
  129.          */
  130.         if (b.psize &&
  131.             (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
  132.             b.psize & sizeof(indx_t) - 1))
  133.             goto einval;
  134.  
  135.         /* Minimum number of keys per page; absolute minimum is 2. */
  136.         if (b.minkeypage) {
  137.             if (b.minkeypage < 2)
  138.                 goto einval;
  139.         } else
  140.             b.minkeypage = DEFMINKEYPAGE;
  141.  
  142.         /* If no comparison, use default comparison and prefix. */
  143.         if (b.compare == NULL) {
  144.             b.compare = __bt_defcmp;
  145.             if (b.prefix == NULL)
  146.                 b.prefix = __bt_defpfx;
  147.         }
  148.  
  149.         if (b.lorder == 0)
  150.             b.lorder = machine_lorder;
  151.     } else {
  152.         b.compare = __bt_defcmp;
  153.         b.cachesize = 0;
  154.         b.flags = 0;
  155.         b.lorder = machine_lorder;
  156.         b.minkeypage = DEFMINKEYPAGE;
  157.         b.prefix = __bt_defpfx;
  158.         b.psize = 0;
  159.     }
  160.  
  161.     /* Check for the ubiquitous PDP-11. */
  162.     if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
  163.         goto einval;
  164.  
  165.     /* Allocate and initialize DB and BTREE structures. */
  166.     if ((t = malloc(sizeof(BTREE))) == NULL)
  167.         goto err;
  168.     memset(t, 0, sizeof(BTREE));
  169.     t->bt_bcursor.pgno = P_INVALID;
  170.     t->bt_fd = -1;            /* Don't close unopened fd on error. */
  171.     t->bt_lorder = b.lorder;
  172.     t->bt_order = NOT;
  173.     t->bt_cmp = b.compare;
  174.     t->bt_pfx = b.prefix;
  175.     t->bt_rfd = -1;
  176.  
  177.     if ((t->bt_dbp = dbp = malloc(sizeof(DB))) == NULL)
  178.         goto err;
  179.     t->bt_flags = 0;
  180.     if (t->bt_lorder != machine_lorder)
  181.         SET(t, B_NEEDSWAP);
  182.  
  183.     dbp->type = DB_BTREE;
  184.     dbp->internal = t;
  185.     dbp->close = __bt_close;
  186.     dbp->del = __bt_delete;
  187.     dbp->fd = __bt_fd;
  188.     dbp->get = __bt_get;
  189.     dbp->put = __bt_put;
  190.     dbp->seq = __bt_seq;
  191.     dbp->sync = __bt_sync;
  192.  
  193.     /*
  194.      * If no file name was supplied, this is an in-memory btree and we
  195.      * open a backing temporary file.  Otherwise, it's a disk-based tree.
  196.      */
  197.     if (fname) {
  198.         switch(flags & O_ACCMODE) {
  199.         case O_RDONLY:
  200.             SET(t, B_RDONLY);
  201.             break;
  202.         case O_RDWR:
  203.             break;
  204.         case O_WRONLY:
  205.         default:
  206.             goto einval;
  207.         }
  208.         
  209.         if ((t->bt_fd =
  210. #ifdef macintosh
  211.             open(fname, flags)) < 0)
  212. #else
  213.             open(fname, flags, mode)) < 0)
  214. #endif
  215.             goto err;
  216.  
  217.     } else {
  218.         if ((flags & O_ACCMODE) != O_RDWR)
  219.             goto einval;
  220.         if ((t->bt_fd = tmp()) == -1)
  221.             goto err;
  222.         SET(t, B_INMEM);
  223.     }
  224.  
  225. #ifndef macintosh
  226.     if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
  227.         goto err;
  228. #endif
  229.  
  230.     if (fstat(t->bt_fd, &sb))
  231.         goto err;
  232.     if (sb.st_size) {
  233. #ifdef macintosh
  234.         nr = read(t->bt_fd, (char *) &m, sizeof(BTMETA));
  235. #else
  236.         nr = read(t->bt_fd, &m, sizeof(BTMETA));
  237. #endif
  238.         if (nr < 0)
  239.             goto err;
  240.         if (nr != sizeof(BTMETA))
  241.             goto eftype;
  242.  
  243.         /*
  244.          * Read in the meta-data.  This can change the notion of what
  245.          * the lorder, page size and flags are, and, when the page size
  246.          * changes, the cachesize value can change too.  If the user
  247.          * specified the wrong byte order for an existing database, we
  248.          * don't bother to return an error, we just clear the NEEDSWAP
  249.          * bit.
  250.          */
  251.         if (m.m_magic == BTREEMAGIC)
  252.             CLR(t, B_NEEDSWAP);
  253.         else {
  254.             SET(t, B_NEEDSWAP);
  255.             BLSWAP(m.m_magic);
  256.             BLSWAP(m.m_version);
  257.             BLSWAP(m.m_psize);
  258.             BLSWAP(m.m_free);
  259.             BLSWAP(m.m_nrecs);
  260.             BLSWAP(m.m_flags);
  261.         }
  262.         if (m.m_magic != BTREEMAGIC || m.m_version != BTREEVERSION)
  263.             goto eftype;
  264.         if (m.m_psize < MINPSIZE || m.m_psize > MAX_PAGE_OFFSET + 1 ||
  265.             m.m_psize & sizeof(indx_t) - 1)
  266.             goto eftype;
  267.         if (m.m_flags & ~SAVEMETA)
  268.             goto eftype;
  269.         b.psize = m.m_psize;
  270.         t->bt_flags |= m.m_flags;
  271.         t->bt_free = m.m_free;
  272.         t->bt_nrecs = m.m_nrecs;
  273.     } else {
  274.         /*
  275.          * Set the page size to the best value for I/O to this file.
  276.          * Don't overflow the page offset type.
  277.          */
  278.         if (b.psize == 0) {
  279.             b.psize = sb.st_blksize;
  280.             if (b.psize < MINPSIZE)
  281.                 b.psize = MINPSIZE;
  282.             if (b.psize > MAX_PAGE_OFFSET + 1)
  283.                 b.psize = MAX_PAGE_OFFSET + 1;
  284.         }
  285.  
  286.         /* Set flag if duplicates permitted. */
  287.         if (!(b.flags & R_DUP))
  288.             SET(t, B_NODUPS);
  289.  
  290.         t->bt_free = P_INVALID;
  291.         t->bt_nrecs = 0;
  292.         SET(t, B_METADIRTY);
  293.     }
  294.  
  295.     t->bt_psize = b.psize;
  296.  
  297.     /* Set the cache size; must be a multiple of the page size. */
  298.     if (b.cachesize && b.cachesize & b.psize - 1)
  299.         b.cachesize += (~b.cachesize & b.psize - 1) + 1;
  300.     if (b.cachesize < b.psize * MINCACHE)
  301.         b.cachesize = b.psize * MINCACHE;
  302.  
  303.     /* Calculate number of pages to cache. */
  304.     ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
  305.  
  306.     /*
  307.      * The btree data structure requires that at least two keys can fit on
  308.      * a page, but other than that there's no fixed requirement.  The user
  309.      * specified a minimum number per page, and we translated that into the
  310.      * number of bytes a key/data pair can use before being placed on an
  311.      * overflow page.  This calculation includes the page header, the size
  312.      * of the index referencing the leaf item and the size of the leaf item
  313.      * structure.  Also, don't let the user specify a minkeypage such that
  314.      * a key/data pair won't fit even if both key and data are on overflow
  315.      * pages.
  316.      */
  317.     t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
  318.         (sizeof(indx_t) + NBLEAFDBT(0, 0));
  319.     if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
  320.         t->bt_ovflsize =
  321.             NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
  322.  
  323.     /* Initialize the buffer pool. */
  324.     if ((t->bt_mp =
  325.         mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
  326.         goto err;
  327.     if (!ISSET(t, B_INMEM))
  328.         mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
  329.  
  330.     /* Create a root page if new tree. */
  331.     if (nroot(t) == RET_ERROR)
  332.         goto err;
  333.  
  334.     /* Global flags. */
  335.     if (dflags & DB_LOCK)
  336.         SET(t, B_DB_LOCK);
  337.     if (dflags & DB_SHMEM)
  338.         SET(t, B_DB_SHMEM);
  339.     if (dflags & DB_TXN)
  340.         SET(t, B_DB_TXN);
  341.  
  342.     return (dbp);
  343.  
  344. einval:    errno = EINVAL;
  345.     goto err;
  346.  
  347. eftype:    errno = EFTYPE;
  348.     goto err;
  349.  
  350. err:    if (t) {
  351.         if (t->bt_dbp)
  352.             free(t->bt_dbp);
  353.         if (t->bt_fd != -1)
  354.             (void)close(t->bt_fd);
  355.         free(t);
  356.     }
  357.     return (NULL);
  358. }
  359.  
  360. /*
  361.  * NROOT -- Create the root of a new tree.
  362.  *
  363.  * Parameters:
  364.  *    t:    tree
  365.  *
  366.  * Returns:
  367.  *    RET_ERROR, RET_SUCCESS
  368.  */
  369. static int
  370. nroot(t)
  371.     BTREE *t;
  372. {
  373.     PAGE *meta, *root;
  374.     pgno_t npg;
  375.  
  376.     if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
  377.         mpool_put(t->bt_mp, meta, 0);
  378.         return (RET_SUCCESS);
  379.     }
  380.     if (errno != EINVAL)
  381.         return (RET_ERROR);
  382.  
  383.     if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
  384.         return (RET_ERROR);
  385.  
  386.     if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
  387.         return (RET_ERROR);
  388.  
  389.     if (npg != P_ROOT)
  390.         return (RET_ERROR);
  391.     root->pgno = npg;
  392.     root->prevpg = root->nextpg = P_INVALID;
  393.     root->lower = BTDATAOFF;
  394.     root->upper = t->bt_psize;
  395.     root->flags = P_BLEAF;
  396.     memset(meta, 0, t->bt_psize);
  397.     mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
  398.     mpool_put(t->bt_mp, root, MPOOL_DIRTY);
  399.     return (RET_SUCCESS);
  400. }
  401.  
  402. #ifdef macintosh
  403. #include <Files.h>
  404. #include <Folders.h>
  405. #include <TFileSpec.h>
  406. #include <Errors.h>
  407.  
  408. typedef struct tfdsc {
  409.     struct tfdsc *    next;
  410.     FSSpec            spec;
  411. } tfdsc;
  412.  
  413. static tfdsc * tempdescs = 0;
  414.  
  415. static void closedescs()
  416. {
  417.     while (tempdescs) {
  418.         HDelete(tempdescs->spec.vRefNum, tempdescs->spec.parID, tempdescs->spec.name);
  419.         
  420.         tempdescs = tempdescs->next;
  421.     }
  422. }
  423.  
  424. /* Create a temporary file in the temp folder. 
  425. */
  426. static int tmp()
  427. {
  428.     static int    id    =    0;
  429.     FSSpec        desc;
  430.     OSErr            err;
  431.     tfdsc *        nudsc;
  432.     
  433.     if (err = FindFolder(kOnSystemDisk, 'temp', true, &desc.vRefNum, &desc.parID))
  434.         return -1;
  435.     
  436.     *((long *) desc.name)        =    '\007tmp';
  437.     
  438.     do {
  439.         desc.name[4]    =    id / 1000     % 10 + '0';
  440.         desc.name[5]    =    id / 100        % 10 + '0';
  441.         desc.name[6]    =    id / 10        % 10 + '0';
  442.         desc.name[7]    =    id             % 10 + '0';
  443.         
  444.         ++id;
  445.         
  446.         err = HCreate(desc.vRefNum, desc.parID, desc.name, 'TEMP', 'TEXT');
  447.     } while (err == dupFNErr);
  448.     
  449.     id = open(FSp2FullPath(&desc), O_RDWR);
  450.     
  451.     if (id < 0)
  452.         return id;
  453.     
  454.     if (!tempdescs)
  455.         atexit(closedescs);
  456.     
  457.     nudsc = malloc(sizeof(tfdsc));
  458.     
  459.     nudsc->next = tempdescs;
  460.     nudsc->spec = desc;
  461.     tempdescs     = nudsc;
  462.     
  463.     return id;
  464. }
  465. #else
  466. static int
  467. tmp()
  468. {
  469.     sigset_t set, oset;
  470.     int fd;
  471.     char *envtmp;
  472.     char path[MAXPATHLEN];
  473.  
  474.     envtmp = getenv("TMPDIR");
  475.     (void)snprintf(path,
  476.         sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : "/tmp");
  477.  
  478.     (void)sigfillset(&set);
  479.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  480.     if ((fd = mkstemp(path)) != -1)
  481.         (void)unlink(path);
  482.     (void)sigprocmask(SIG_SETMASK, &oset, NULL);
  483.     return(fd);
  484. }
  485. #endif
  486.  
  487. static int
  488. byteorder()
  489. {
  490.     u_long x;            /* XXX: 32-bit assumption. */
  491.     u_char *p;
  492.  
  493.     x = 0x01020304;
  494.     p = (u_char *)&x;
  495.     switch (*p) {
  496.     case 1:
  497.         return (BIG_ENDIAN);
  498.     case 4:
  499.         return (LITTLE_ENDIAN);
  500.     default:
  501.         return (0);
  502.     }
  503. }
  504.  
  505. int
  506. __bt_fd(dbp)
  507.         const DB *dbp;
  508. {
  509.     BTREE *t;
  510.  
  511.     t = dbp->internal;
  512.  
  513.     /* Toss any page pinned across calls. */
  514.     if (t->bt_pinned != NULL) {
  515.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  516.         t->bt_pinned = NULL;
  517.     }
  518.  
  519.     /* In-memory database can't have a file descriptor. */
  520.     if (ISSET(t, B_INMEM)) {
  521.         errno = ENOENT;
  522.         return (-1);
  523.     }
  524.     return (t->bt_fd);
  525. }
  526.